package com.kevin.Code.Math;

/**
 * @author Vinlee Xiao
 * @Classname Sqrtx
 * @Description Leetcode 69. Sqrt(x) 简单 没思路 二分法为好的思路
 * @Date 2021/10/28 20:08
 * @Version 1.0
 */
public class Sqrtx {

    /**
     * @param x
     * @return
     */
    public int mySqrt(int x) {

//        if (x == 0) {
//            return 0;
//        }

        int low = 0;
        int high = x;


        while (low <= high) {
            int mid = (low + high) / 2;
//            System.out.println(mid);
            //可能造成溢出
            if ((long) (mid * mid) <= x) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }

        }
//        System.out.println(low);
//        System.out.println(high);

        return high;
    }

    /**
     * @param x
     * @return
     */
    public int mySqrt1(int x) {

        int res = (int) Math.exp(0.5 * Math.log(x));


        return (long) (res + 1) * (res + 1) <= x ? res + 1 : res;
    }


    public static void main(String[] args) {
        Sqrtx sqrtx = new Sqrtx();
        int i = sqrtx.mySqrt(0);
        System.out.println(i);
    }
}
